(1) Field of Invention
The present invention relates to an object group recognition and tracking system, and more particularly, to a object recognition and tracking system that utilizes graph-matching to identify and track groups of objects.
(2) Related Art
Typical approaches to graph matching include different tree search algorithms such as sequential tree searches and branch and bound searches. Such techniques are described by L. Shapiro and R. M. Haralick, in “Structural description and inexact matching,” IEEE PAMI 3(5), 504-519, 1981, and by W. H. Tsai and K. S. Fu, in “Error-correcting isomorphism of attributed relational graphs for pattern analysis,” IEEE MSC, 9, 757-768, 1979.
Other approaches define an objective function and solve a continuous optimization problem to find the global minima. Such techniques were described by 3. S. Gold and A. Rangarajan, in “A graduated assignment algorithm for graph matching,” IEEE PAMI, 18, 309-319, April 1996, and by S. Medasani and R. Krishnapuram, in “Graph Matching by Relaxation of Fuzzy Assignments,” IEEE Transactions on Fuzzy Systems, 9(1), 173-183, February 2001.
Additionally, in a publication by A. D. J Cross, R. C. Wilson, and E. R. Hancock, entitled, “Inexact graph matching using genetic search,” Pattern Recognition, 30(6), 953-970, 1997, the authors have shown that using genetic search methods for inexact matching problems outperforms conventional optimization methods such as gradient descent and simulated annealing.
Furthermore, in a publication by K. G. Khoo and P. N. Suganthan, entitled, “Structural Pattern Recognition Using Genetic Algorithms with Specialized Operators,” IEEE Trans. On Systems, Man, and Cybernetics-Part B, 33(1), February 2003, the authors attempt to improve genetic algorithm (GA) based graph-matching procedures leading to more accurate mapping and faster convergence. The population solutions are represented by integer strings indicating the mapping between source and target graphs.
Graphs of various types have been widely used as representational tools in many applications such as object recognition, knowledge representation and scene description. Fuzzy attributed relational graphs (FARGs) are a powerful way to model the inherent uncertainty in several of the above domains. FARGs have been described by R. Krishnapuram, S. Medasani, S. Jung and Y. Choi, in “FIRST—A Fuzzy Information Retrieval System,” IEEE Trans. On Knowledge and Data Engineering, October 2004, and in the article entitled, “Graph Matching by Relaxation of Fuzzy Assignments.” The computational complexity of graph isomorphism is still an open question, i.e., whether it belongs to the Polynomial (P) or Nondeterministic-Polynomial (NP) class of problems. However, the problem of sub-graph isomorphism and inexact graph matching is known to be a member of the NP-complete class for which it is widely believed that only exponentially complex deterministic solutions exist.
A need exists to solve this hard combinatorial problem non-deterministically by using ideas from evolutionary systems. Most of the previous approaches use a single solution that is altered heuristically by minimizing an objective function or stochastically modifying the solution. Therefore, a need further exists to employ a population of potential solutions that interact to find the optimum solution for the particular problem at hand. The present invention solves such a need by using a population of agents that search the solution space and cooperatively find the optimum solution.